package code101_200.code10_20;

import com.sun.source.tree.Tree;

import java.util.Stack;

/**
 * 路径总和
 *
 * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，
 * 这条路径上所有节点值相加等于目标和 targetSum 。
 *
 * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
 * 输出：true
 */
public class _112hasPathSum {

    /**
     * 思考：1. 动态规划问题，可划分为子问题。
     * 2. 由于是2叉树，可将树的val值利用起来，表示根节点到此路径的值，判断有没有等于目标值即可。时间N，空间1
     *
     * 一次通过，但效率低。
     * 执行用时：     * 1 ms     * , 在所有 Java 提交中击败了     * 15.66%     * 的用户
     * 内存消耗：     * 38.4 MB     * , 在所有 Java 提交中击败了     * 23.03%     * 的用户
     *
     * @param root ： 根节点
     * @param targetSum ： 路径总和，查看是否存在此路径
     * @return
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node;
        if(root==null) return false;
        int sum;
        stack.push(root);
        while (stack.size()!=0){
            node = stack.pop();
            sum = node.val;
            if(node.val==targetSum&&node.left==null&&node.right==null) return true;
            if(node.left!=null){
                node.left.val += sum;
                stack.push(node.left);
            }
            if(node.right!=null){
                node.right.val += sum;
                stack.push(node.right);
            }
        }
        return false;
    }

}
